package main.old.new_2023.last.month_6;

/**
 * @Description:
 * //TODO 剑指 Offer 22. 链表中倒数第k个节点
    * 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
    * 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

 * //todo 剑指 Offer 25. 合并两个排序的链表
    * 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

 * //todo 1170. 比较字符串最小字母出现频次
    * 定义一个函数 f(s)，统计 s  中（按字典序比较）最小字母的出现频次 ，其中 s 是一个非空字符串。
    * 例如，若 s = "dcce"，那么 f(s) = 2，因为字典序最小字母是 "c"，它出现了 2 次。
    * 现在，给你两个字符串数组待查表 queries 和词汇表 words 。对于每次查询 queries[i] ，需统计 words 中满足 f(queries[i]) < f(W) 的 词的数目 ，W 表示词汇表 words 中的每个词。
    * 请你返回一个整数数组 answer 作为答案，其中每个 answer[i] 是第 i 次查询的结果。

 * //todo 剑指 Offer 52. 两个链表的第一个公共节点
    * 输入两个链表，找出它们的第一个公共节点。
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/5
 * @Param:
 * @return:
 **/
public class Solution0610 {

    //两个链表的第一个公共节点
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //使用hashset，a链表每一个都放入set，顺序判断b有没有一样的，有的话就是了
        //实现过了，换一种实现

        //双指针，一个指 a,一个指b，同时移动，如果 a 和 b 有相同节点 c 那 ，
        //a-c =m, b-c = n,  假设a移动完，指针移到b，b移动完到a，那  a-m = b-n => a+n = b+m
        //移动完a 节点+ b的不重合部分 ==  b节点 + a的不重合部分
        if (headA == null || headB == null) {
            return null;
        }
        ListNode a = headA;
        ListNode b = headB;

        while (a != b){
            if (a == null){
                a = headB;
            }else {
                a = a.next;
            }
            if (b == null){
                b = headA;
            }else {
                b = b.next;
            }
        }
        return a;

    }

    //比较字符串最小字母出现频次
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] countWord = new int[12];
        //计算 words 的 出现次数，数组
        for (int i = 0;i < words.length;i++){
            countWord[f(words[i])] ++;
        }
        //前面的把后面的都加上，直接
        for (int i = 9; i > 0;i--){
            countWord[i] += countWord[i+1];
        }
        int[] res = new int[queries.length];
        for (int i = 0;i< queries.length;i++){
            res[i] =  countWord[f(queries[i]) + 1];
        }
        return res;
    }
    public int f(String s){
        char c = 'z';
        int count = 0;
        for (char temp:s.toCharArray()){
            if (c > temp){
                c= temp;
                count = 1;
            }else if (c == temp){
                count ++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution0610 solu = new Solution0610();
        String[] queries = {"cbd"};
        String[] words = {"zaaaz"};
        int[] ints = solu.numSmallerByFrequency(queries, words);
        System.out.println(ints);

    }

    //合并两个排序的链表
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //虚拟节点
        ListNode dum = new ListNode(0);
        ListNode cur = dum;

        while (l1 != null && l2 != null){
            if (l1.val > l2.val){
                cur.next = l2;
                l2 = l2.next;
            }else {
                cur.next = l1;
                l1 = l1.next;
            }
            cur = cur.next;
        }
        if (l1 != null){
            cur.next = l1;
        }else {
            cur.next = l2;
        }
        return dum.next;
    }

    //链表中倒数第k个节点
    public ListNode getKthFromEnd(ListNode head, int k) {
        //双指针，第一个指针先走 k 步，第二个指针从头出发，第一个走到null返回第二个

        ListNode first = head;
        ListNode second = head;
        for(int i = 0; i < k; i++){
            second = second.next;
        }

        while (second != null){
            second = second.next;
            first = first.next;
        }
        return first;
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }


}
